//GA
//$Id: ga_common.h 441 2010-04-09 17:27:20Z Oleg.Bulychov $
#pragma once

//__________________________________________________________________________________
#include "src/heo/include/random.h"
#include "src/heo/include/stream_visitor.h"
#include "src/heo/include/xml_file.h"
#include "src/heo/include/ref_ptr.h"
#include "src/heo/include/factory.h"
#include "src/heo/include/optimization_direction.h"
#include "src/heo/include/solution.h"
#include "src/heo/include/stop_condition.h"
#include "src/heo/include/stream_visitor.h"
#include "src/heo/include/selection.h"
//__________________________________________________________________________________
//__________________________________________________________________________________
namespace ga
{

namespace selection
{

template<class E, class T, class D>
struct abstract_selection:
    public ref_object
{
    virtual void init(T** list, int size, E* env, uniform_random& rnd) = 0;

    virtual T* select_One(T** src, int src_size, E* env, uniform_random& rnd) = 0;

    virtual void select(T** dst, int dst_size, T** src, int src_size, E* env, uniform_random& rnd) = 0;
};

template<class E, class T, class D>
class tournament_selection:
    public factory_object< tournament_selection<E, T, D>, abstract_selection<E, T, D> >,
    public Selection_Tournament<D>
{
public://TODO fix me:
    int tournament_size_;
    typedef Selection_Tournament<D> TBase;
public:
    explicit tournament_selection()
    {
        accept(meta::set_default_values());
    }

    static char const* get_Name() { return "tournament"; }

    template<class V>
    void accept(V& v)
    {
        v(VAR_(tournament_size), meta::validator(3, 1, std::numeric_limits<int>::max()));
    }

    virtual void init(T** list, int size, E* env, uniform_random& rnd)
    {
        TBase::init(list, size);
    }

    virtual T* select_One(T** src, int src_size, E* env, uniform_random& rnd)
    {
        //TODO fix me: *this is suxx
        return TBase::select_One(src, src_size, *this, rnd);
    }

    virtual void select(T** dst, int dst_size, T** src, int src_size, E* env, uniform_random& rnd)
    {
        //TODO fix me: *this is suxx
        TBase::select(dst, dst_size, src, src_size, *this, rnd);
    }
};

template<class E, class T, class D>
class roulette_selection:
    public factory_object< roulette_selection<E, T, D>, abstract_selection<E, T, D> >,
    public Selection_Roulette<D>
{
public:
    typedef Selection_Roulette<D> TBase;
public:
    static char const* get_Name() { return "roulette"; }

    template<class V>
    void accept(V& v)
    {}

    virtual void init(T** list, int size, E* env, uniform_random& rnd)
    {
        TBase::init(list, size);
    }

    virtual T* select_One(T** src, int src_size, E* env, uniform_random& rnd)
    {
        //TODO fix me: *this is suxx
        return TBase::select_One(src, src_size, *this, rnd);
    }

    virtual void select(T** dst, int dst_size, T** src, int src_size, E* env, uniform_random& rnd)
    {
        //TODO fix me: *this is suxx
        TBase::select(dst, dst_size, src, src_size, *this, rnd);
    }
};

template<class E, class T, class D>
class random_selection:
    public factory_object< random_selection<E, T, D>, abstract_selection<E, T, D> >,
    public Selection_Random<D>
{
public:
    typedef Selection_Random<D> TBase;
public:
    static char const* get_Name() { return "random"; }

    template<class V>
    void accept(V& v)
    {}

    virtual void init(T** list, int size, E* env, uniform_random& rnd)
    {
        TBase::init(list, size);
    }

    virtual T* select_One(T** src, int src_size, E* env, uniform_random& rnd)
    {
        //TODO fix me: *this is suxx
        return TBase::select_One(src, src_size, *this, rnd);
    }

    virtual void select(T** dst, int dst_size, T** src, int src_size, E* env, uniform_random& rnd)
    {
        //TODO fix me: *this is suxx
        TBase::select(dst, dst_size, src, src_size, *this, rnd);
    }
};

template<class X>
struct validator: public meta::abstract_validator
{
    template<class U>
    void set_Default(ref_ptr<U>& t) const
    {
        X* px = new X;
        t.attach(px);
    }
};

}//:selection


namespace inter_operator
{

template<class E, class T>
struct abstract_operator:
    public ref_object
{
    virtual void apply(T** list, int size,
        E* env,
        int rank,
        int thread_id,
        int step,
        int max_step,
        uniform_random& rnd) = 0;
};

template<class E, class T>
class crossover:
    public factory_object< crossover<E, T>, abstract_operator<E, T> >
{
    double probability_;
public:
    explicit crossover()
    {
        accept(meta::set_default_values());
    }

    static char const* get_Name() { return "crossover"; }

    template<class V>
    void accept(V& v)
    {
        v(VAR_(probability), 0.3);
    }

    virtual void apply(T** list, int size,
        E* env,
        int rank,
        int thread_id,
        int step,
        int max_step,
        uniform_random& rnd)
    {
        //KProfiler pr("cross");
        for (int i = 0; i < size - 1; i += 2)
        {
            if (rnd.next_Double() < probability_)
                list[i]->cross(env, rnd, *list[i + 1]);
        }
    }
};

template<class E, class T>
class mutation:
    public factory_object< mutation<E, T>, abstract_operator<E, T> >
{
    double probability_;
    bool fadeout_;
public:
    explicit mutation()
    {
        accept(meta::set_default_values());
    }

    static char const* get_Name() { return "mutation"; }

    template<class V>
    void accept(V& v)
    {
        v(VAR_(probability),   0.003);
        v(VAR_(fadeout),       false);
    }

    virtual void apply(T** list, int size,
        E* env,
        int rank,
        int thread_id,
        int step,
        int max_step,
        uniform_random& rnd)
    {
        //KProfiler pr("mutate");
        //:reduce mutation level by time
        double m = probability_;
        if (fadeout_)
            m *= (exp(exp(4. * log(1. - (step - 1) / max_step))) - 1.);
        for (int i = 0; i < size; ++i)
        {
            list[i]->mutate(env, rnd, m);
        }
    }
};

}//:inter_operator

}//:ga


struct validator_ga_tag
{};

template<class E, class T, class Q>
struct validator_ga
{
};

template<class E, class T>
struct validator_ga<E, T, validator_ga_tag>: public meta::abstract_validator
{
    template<class U>
    void set_Default(std::vector< ref_ptr<U> >& v) const
    {
        v.clear();
        ref_ptr<U> pt;
        using namespace ga::inter_operator;
        {
            crossover<E, T>* px = new crossover<E, T>;
            pt.attach(px);
            v.push_back(pt);
        }
        {
            mutation<E, T>* px = new mutation<E, T>;
            pt.attach(px);
            v.push_back(pt);
        }
    }
};

template<class E, class V = validator_ga_tag>
struct GA_Traits
{
    typedef E TEnvironment;
    typedef V TValidatorTag;
};

struct ga_tag
{};

template<class T>
class GA
{
    DISALLOW_COPY_AND_ASSIGN(GA);
public:
    typedef typename T::TEnvironment TEnvironment;
    typedef solution<typename TEnvironment::TSolution, ga_tag> TSolution;

    typedef typename TSolution::TDirection TDirection;
    typedef typename TSolution::TCostType  TCostType;
protected:
    TEnvironment*           env_;
    int                     rank_;
    uniform_random          rnd_;

    int                     population_size_;
    int                     offspring_size_;
    int                     output_size_;
    bool                    only_offspring_;

    std::vector< ref_ptr< stop_condition::abstract_stop_condition<TEnvironment,
        TSolution> > > stop_condition_;
    int                     max_step_;
    int                     pending_stop_;
    int                     sent_stop_;

    ref_ptr< ga::selection::abstract_selection<TEnvironment, TSolution, TDirection> > parent_selection_;
    ref_ptr< ga::selection::abstract_selection<TEnvironment, TSolution, TDirection> > offspring_selection_;

    std::vector< ref_ptr< ga::inter_operator::abstract_operator<TEnvironment, TSolution> > > operator_list_;

//:TODO where it should be:
    ref_ptr< ga::selection::abstract_selection<TEnvironment, TSolution, TDirection> >
                            emigrate_selection_;
    ref_ptr< ga::selection::abstract_selection<TEnvironment, TSolution,
        typename inverted_direction<TDirection>::result> >
                            immigrate_selection_;
    int                     migration_size_;//?
    TCostType               best_fitness_;
    TCostType               prev_fitness_;
    bool                    prev_fitness_init_;

    TSolution               tmp_;
    TSolution**             parent_;
    TSolution**             offspring_;
    TSolution**             common_;
    TSolution**             migrant_list_;
public:
    explicit GA(): env_(NULL),
        rank_(0),
        rnd_(0),
        max_step_(0),
        pending_stop_(0),
        sent_stop_(0),
        best_fitness_(),
        prev_fitness_(),
        prev_fitness_init_(),
        parent_(NULL),
        offspring_(NULL),
        common_(NULL),
        migrant_list_(NULL)
    {
        stop_condition::max_step<TEnvironment, TSolution>::instantiate();
        stop_condition::cost_limit<TEnvironment, TSolution>::instantiate();
        hidden::instantiate_ptr_visit((stop_condition::max_step<TEnvironment, TSolution>*)0, 0, hidden::adl_tag());
        hidden::instantiate_ptr_visit((stop_condition::cost_limit<TEnvironment, TSolution>*)0, 0, hidden::adl_tag());
    }

    static char const* get_Name() { return "ga"; }

    template<class V>
    void accept(V& v)
    {
        v(VAR_(population_size),            meta::validator(30, 1, std::numeric_limits<int>::max()));
        v(VAR_(offspring_size),             meta::validator(50, 1, std::numeric_limits<int>::max()));
        v(VAR_(only_offspring),             false);
        v(VAR_(output_size),                meta::validator(1,  1, population_size_));

        v(VAR_(migration_size),             3);

        v(VAR_(parent_selection),           ga::selection::validator<
            ga::selection::tournament_selection<TEnvironment,
                TSolution, TDirection> > ());
        v(VAR_(offspring_selection),        ga::selection::validator<
            ga::selection::tournament_selection<TEnvironment,
                TSolution, TDirection> >());

        v(VAR_(emigrate_selection),        ga::selection::validator<
            ga::selection::tournament_selection<TEnvironment,
                TSolution, TDirection> >());
        v(VAR_(immigrate_selection),        ga::selection::validator<
            ga::selection::tournament_selection<TEnvironment,
                TSolution, typename inverted_direction<TDirection>::result> >());

        v(operator_list_, "operator",       validator_ga<TEnvironment, TSolution, typename T::TValidatorTag>());

        v(VAR_(stop_condition),             stop_condition::validator<
            stop_condition::max_step<TEnvironment, TSolution> >());
    }

    TEnvironment* get_Environment() const { return env_; }

    int get_Rank() const { return rank_; }

    int pending_Stop() const { return pending_stop_; }

    uniform_random& get_Rnd() { return rnd_; }

    template<template<class, class, class> class S>
    static void register_Selection()
    {
        S<TEnvironment, TSolution, TDirection>::instantiate();
        hidden::instantiate_ptr_visit((S<TEnvironment, TSolution, TDirection>*)0, 0, hidden::adl_tag());
        S<TEnvironment, TSolution,
            typename inverted_direction<TDirection>::result>::instantiate();
        hidden::instantiate_ptr_visit((S<TEnvironment, TSolution,
            typename inverted_direction<TDirection>::result>*)0, 0, hidden::adl_tag());
    }


    template<template<class, class> class O>
    static void register_Operator()
    {
        O<TEnvironment, TSolution>::instantiate();
        hidden::instantiate_ptr_visit((O<TEnvironment, TSolution>*)0, 0, hidden::adl_tag());
    }


    void init(TEnvironment* env, int rank, int thread_id)
    {
        if (!env_)
        {
            env_ = env;
            rank_ = rank;
            rnd_.set_Thread_Id(thread_id);
            tmp_.init(env_, rnd_);
        }
        else
        {
            ASSERT_(env_ == env);
            ASSERT_(rank_ == rank);
        }
    }

    int get_Default_Solution_Pool_Size() const
    {
        return population_size_;
    }

    template<class TInOutSolution>
    void init_From_Pool(Solution_Pool<TInOutSolution>& pool)
    {
        ASSERT_(!parent_);
        //ASSERT_(pool.sol_list_.empty() || pool.sol_list_.size() == (size_t)population_size_);

        parent_ = new TSolution*[population_size_];
        offspring_ = new TSolution*[offspring_size_];

        if (!only_offspring_)
            common_ = new TSolution*[population_size_ + offspring_size_];
        if (migration_size_)
            migrant_list_ = new TSolution*[migration_size_];

        typename Solution_Pool<TInOutSolution>::iterator it = pool.sol_list_.begin();
        for (int i = 0; i < population_size_; ++i)
        {
            parent_[i] = new TSolution;
            parent_[i]->init(env_, rnd_);
            if (it != pool.sol_list_.end())
            {
                parent_[i]->assign(*it);
                ++it;
            }
            else
            {
                parent_[i]->generate(env_, rnd_);
            }
            if (common_)
                common_[i] = parent_[i];
        }
        for (int i = 0; i < offspring_size_; ++i)
        {
            offspring_[i] = new TSolution;
            offspring_[i]->init(env_, rnd_);
            if (common_)
                common_[i + population_size_] = offspring_[i];
        }
    }

    ~GA()
    {
        if (parent_)
        {
            for (int i = 0; i < population_size_; ++i)
                delete parent_[i];
            delete [] parent_;
        }
        if (offspring_)
        {
            for (int i = 0; i < offspring_size_; ++i)
                delete offspring_[i];
            delete [] offspring_;
        }
        delete[] common_;
        delete[] migrant_list_;
    }

    void select_Parents()
    {
        //KProfiler pr("sel par");

        parent_selection_->init(parent_, population_size_, env_, rnd_);
        parent_selection_->select(offspring_, offspring_size_, parent_, population_size_, env_, rnd_);
    }

    void select_Offsprings()
    {
        //KProfiler pr("sel offs");
        TSolution** src = offspring_;
        int src_size = offspring_size_;
        if (common_)
        {
            src = common_;
            src_size += population_size_;
        }

        offspring_selection_->init(src, src_size, env_, rnd_);
        offspring_selection_->select(parent_, population_size_, src, src_size, env_, rnd_);
    }

    void evaluate_Parents()
    {
        for (int i = 0; i < population_size_; ++i)
        {
            parent_[i]->evaluate(env_, rnd_);
        }
    }

    void evaluate_Offsprings()
    {
        for (int i = 0; i < offspring_size_; ++i)
        {
            offspring_[i]->evaluate(env_, rnd_);
        }
    }

    void apply_Intra_Operators(int step)
    {
        for (size_t i = 0; i < operator_list_.size(); ++i)
        {
            operator_list_[i]->apply(offspring_, offspring_size_,
                env_, rank_, rnd_.get_Thread_Id(),
                step, max_step_,
                rnd_);
        }
    }

    void update_Best_Fitness()
    {
        TCostType fitness = parent_[0]->get_Fitness();
        for (int i = 1; i < population_size_; ++i)
        {
            TCostType f =  parent_[i]->get_Fitness();
            if (TDirection()(f, fitness))
            {
                fitness = f;
            }
        }
        best_fitness_ = fitness;
    }

    void show_Progress(int step)
    {
        if (rank_ >= env_->debug_level_)
            return;

#pragma omp critical(debug_output)
        if (prev_fitness_init_)
        {
            if (TDirection()(prev_fitness_, best_fitness_))
            {
                std::cout << std::setw(2) << rank_ << ":" << std::setw(5) << step << "<<<WORSE: " << best_fitness_ <<
                    " -" << Abs(best_fitness_ - prev_fitness_) << std::endl;
            }
            else if (TDirection()(best_fitness_, prev_fitness_))
            {
                std::cout << std::setw(2) << rank_ << ":" << std::setw(5) << step << ">>>BETTER: " << best_fitness_ <<
                    " +" << Abs(best_fitness_ - prev_fitness_) << std::endl;
                prev_fitness_ = best_fitness_;
            }
            else
            {
                std::cout << std::setw(2) << rank_ << ":" << std::setw(5) << step << "===SAME: " << best_fitness_ << std::endl;
            }
        }
        else
        {
            std::cout << std::setw(2) << rank_ << ":" << std::setw(5) << step << "###INITIAL: " << best_fitness_ << std::endl;
            prev_fitness_ = best_fitness_;
            prev_fitness_init_ = true;
        }
    }

    template<class Send>
    void emigrate(Send& out)
    {
        //:_sleep(100);
        emigrate_selection_->init(parent_, population_size_, env_, rnd_);
        for (int i = 0; i < migration_size_; ++i)
        {
            TSolution* pt = emigrate_selection_->select_One(parent_, population_size_, env_, rnd_);
            out << *pt;
        }
    }

    template<class Recv>
    void immigrate(Recv& in)
    {
        {
            immigrate_selection_->init(parent_, population_size_, env_, rnd_);
            for (int i = 0; i < migration_size_; ++i)
            {
                TSolution* pt = immigrate_selection_->select_One(parent_, population_size_, env_, rnd_);
                migrant_list_[i] = pt;
            }
        }
        //:additional migrant_list_ is used becoz
        //:sel may be invalid after pt->assign

        for (int i = 0; i < migration_size_; ++i)
        {
            in >> tmp_;
            TSolution* pt = migrant_list_[i];
            if (TDirection()(tmp_.get_Fitness(), pt->get_Fitness()))
                pt->assign(tmp_);
        }
    }

    template<class Send>
    void send_Stop(Send& out)
    {
        out << pending_stop_;
        if (pending_stop_)
        {
            sent_stop_ = 1;
            if (rank_ < env_->debug_level_)
            {
#pragma omp critical(debug_output)
                std::cout << rank_ << ": stop sent" << lf;
            }
        }
    }

    template<class Recv>
    void recv_Stop(Recv& in)
    {
        int stop = 0;
        in >> stop;
        if (stop)
        {
            pending_stop_ = 1;
            if (rank_ < env_->debug_level_)
            {
#pragma omp critical(debug_output)
                std::cout << rank_ << ": stop received" << lf;
            }
        }
    }

    bool stop(int nStep)
    {
        for (size_t i = 0; i < stop_condition_.size(); ++i)
        {
            if (stop_condition_[i]->stop(*env_, best_fitness_, nStep))
                return true;
        }
        return false;
    }

    void calc_Max_Step()
    {
        max_step_ = INT_MAX;
        for (size_t i = 0; i < stop_condition_.size(); ++i)
        {
            int t = stop_condition_[i]->get_Max_Step();
            if (t < max_step_)
                max_step_ = t;
        }
    }

    void sort_Population()
    {
        std::sort(parent_, parent_ + population_size_, Greater_Solution);
    }

    static bool Greater_Solution(TSolution const* pLeft, TSolution const* pRight)
    {
        TCostType fa = pLeft->get_Fitness();
        TCostType fb = pRight->get_Fitness();
        return (fa > fb);
    }

    //template<class TInOutSolution>
    //void solve(TInOutSolution& sol)
    //{
    //    generate_Random_Population();
    //    evaluate_Parents();

    //    for (int step = 1; !stop_condition_.stop(step); ++step)
    //    {
    //        select_Parents();

    //        apply_Intra_Operators(step);

    //        evaluate_Offsprings();
    //        
    //        select_Offsprings();
    //        update_Solution(sol, step);
    //    }
    //}
};
//__________________________________________________________________________________
//__________________________________________________________________________________

//EOF!
